package tezhongbing;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

import org.apache.commons.lang.math.RandomUtils;
/**
 * 相对优先排序和绝对优先排序的效率比较
 * @author zhaoyujie
 *相对优先排序就是下标位置为k的元素和k/2位置的元素比较，如果k位置的元素小于k/2位置的元素，就互换。按照这个规则继续向前比较。
 *相对排序比绝对排序的效率高，并且随着要排序元素数量的增加，效率的差距越大。
 */
public class RelativeAndAbsoluteSort {
	private static List<Integer> list = new ArrayList<Integer>();
	private static List<Integer> list2 = new ArrayList<Integer>();
	public static void main(String[] args) {
		for(int i=0;i<100000;i++){
			list.add(RandomUtils.nextInt());
		}
		list2.addAll(list);
		
		sortRelativeList();
		sortAbsoluteList();
	}

	private static void sortAbsoluteList() {
		long begin = System.currentTimeMillis();
		Collections.sort(list2, new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				return o1-o2;
			}
		});
		long end = System.currentTimeMillis();
		System.out.println("绝对优先排序用时："+(end-begin)+"毫秒");
	}

	private static void sortRelativeList() {
		long begin = System.currentTimeMillis();
		for (int i = 0; i < list.size(); i++) {
			siftUp(i);
		}
		long end = System.currentTimeMillis();
		System.out.println("相对优先排序用时："+(end-begin)+"毫秒");
	}
	
	private static void siftUp(int k) {
		Integer x = list.get(k);
        while (k > 0) {
            int parent = (k - 1) >>> 1;
            Integer e = list.get(parent);
            if (x >= e)
                break;
            list.set(k, e);
            k = parent;
        }
        list.set(k, x);
    }
	
}
